package wheel.arithmetic;

import cn.hutool.core.util.ArrayUtil;
import cn.hutool.core.util.RandomUtil;
import org.omg.CORBA.ARG_IN;

import java.util.Arrays;

/**
 * 归并排序-二路归并排序
 *
 *
 *
 * 算法策略，分而治之，递归。
 */
public class TwoMergeSort {

    public static void main(String[] args) {

        Integer[] arr = new Integer[100000000];
        for(int i=0; i<arr.length; i++){
            arr[i] = RandomUtil.randomInt(0, arr.length);
        }

//        arr = new Integer[]{10, 9, 8, 7, 6, 5, 4, 3};


//        System.out.println("输入: "+ ArrayUtil.toString(arr));


        long startTime = System.currentTimeMillis();
        arr = execute(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("耗时: "+(endTime-startTime)+"ms");
//        System.out.println("输出: "+ ArrayUtil.toString(arr));


        verifyDataCorrect(arr);


    }

    private static void verifyDataCorrect(Integer[] arr){
        Integer upValue = null;
        for(int i=0; i<arr.length; i++){
            int currValue = arr[i];
            if(upValue==null){
                upValue =currValue;
                continue;
            }
            if(upValue > currValue)
                throw new RuntimeException("算法输出结果不正确！！  数据下标: "+(i-1));
            upValue = currValue;
        }
        System.out.println("算法输出结果校验通过！！");
    }



    public static Integer[] execute(Integer[] arr){
        int len = arr.length;

        if(len<50){
            return SimpleInsertSort.execute(arr);
        }else{
            int halfSize = len>>1;
            Integer[] leftArr = Arrays.copyOfRange(arr, 0, halfSize);
            Integer[] rightArr = Arrays.copyOfRange(arr, halfSize-1, len-1);    //TODO 不太明白这个from为什么不是halfSize, 而是halfSize-1????

            leftArr = execute(leftArr);
            rightArr = execute(rightArr);

//            System.out.println(arr.length+","+leftArr.length+","+rightArr.length);


            Integer leftIndex=0, rightIndex=0;
            for(int i=0; i<len; i++){
                if(leftIndex==leftArr.length){
//                    try {
                        arr[i] = rightArr[rightIndex++];
//                    }catch(Exception e){
//                        e.printStackTrace();
//                    }
                    continue;
                }

                if(rightIndex==rightArr.length){
                    arr[i] = leftArr[leftIndex++];
                    continue;
                }


                if(leftArr[leftIndex]<=rightArr[rightIndex]){ //用“<=”就使算法的稳定性成立了？
                    arr[i] = leftArr[leftIndex++];
                }else{
                    arr[i] = rightArr[rightIndex++];
                }
            }

            return arr;
        }

    }

    //耗时: 84ms 十万个
    //耗时: 685ms 一百万个
    //耗时: 7237ms 一千万个， 比堆排序还快三秒左右。
    //排序一亿个时，太吃内存、太耗时间了，CPU几乎满载。



}
